package com.favorite;

public class Solution215 {
    public int findKthLargest(int[] nums, int k) {
        int i = 0;
        int j = nums.length - 1;
        while (true) {
            int index = quickSort(nums, i, j);
            if (index == nums.length - k) return nums[index];
            else if (index < nums.length - k) {
                i = index + 1;
            } else {
                j = index - 1;
            }
        }
    }

    public int quickSort(int[] nums, int l, int r) {
        if (l >= r) return l;
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && nums[j] >= nums[l]) j--;
            while (i < j && nums[i] <= nums[l]) i++;
            swap(nums, i, j);
        }
        swap(nums, i, l);
        return i;
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
